// 子集：如果集合A的任意元素都是集合S的元素，则称集合A是集合S的子集
// 给定一个集合S，枚举其所有可能的子集

// 这里介绍一个枚举子集的方法，二进制枚举子集算法
// 思路：对于元素个数为n的集合S，每个元素都有选取和未选取两种状态，我们用1表示选取该元素，用0表示不选取该元素
// 这样我们可以用长度为n的二进制数来表示集合S或者表示S的子集，其中二进制的每一位数都对应了集合中某一个元素的选取状态
// 对于长度为5的集合S，我们只需要从00000-11111枚举一次，即可得到长度为5的集合的所有子集
// 对于长度为n的集合S，只需要枚举2的n次，即可得到所有子集

function subSets(S) {
    let n = S.length  //n为集合S的个数
    let sub_sets = [] // 用来保留所有子集
    for (let i = 0; i < 1 << n ; i++) { // 枚举 0 -2的n次 减 1
        let set = [] // 保存当前子集
        for (let j = 0; j < n; j++) { // 枚举第i位元素
            if (i >> j & 1) { // 如果第i位元素对应的二进制位为1，表示选取该元素
                set.push(S[j])
            }            
        }
        sub_sets.push(set)
    }
    return sub_sets  // 返回所有子集
}

let arr = [1, 2, 3]
console.log(subSets(arr));